class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        unordered_map<int, int> mp;
        int n = arr.size();
        double rate = 0.25 * n;
        for (int i = 0; i < n; i++) {
            ++mp[arr[i]];
            if (mp[arr[i]] > rate) return arr[i];
        }
        return 0;
    }
};
